package map;

import java.util.LinkedList;
import java.util.List;

/**
 * @title:
 * @description:
 * @Author 易俊杰
 * @data: 2022/8/10 14:53
 * @version: V1.0
 */
public class LeetCode797 {

    public static void main(String[] args) {
        int[][] graph = {{1, 2}, {3}, {3}, {}};
        List<List<Integer>> res = new LeetCode797().allPathsSourceTarget(graph);
        System.out.println(res);
    }

    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        LinkedList<Integer> track = new LinkedList<>();
        traverse(graph, 0, track);
        return res;
    }

    void traverse(int[][] graph, int s, LinkedList<Integer> track) {

        track.addLast(s);
        if (s == graph.length - 1) {
            res.add(new LinkedList<>(track));
            track.removeLast();
            return;
        }
        for (Integer v : graph[s]) {
            traverse(graph, v, track);
        }
        track.removeLast();

    }
}
